package 树;

import java.util.Deque;
import java.util.LinkedList;

public class Leedcode958二叉树的完全性检验 {
    public boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean isSecType = false;
        while (!queue.isEmpty()){
            //取出对头元素
            TreeNode node = queue.poll();
           if (!isSecType){
               //对头的左右子节点都不为空
               if (node.left != null && node.right != null){
                   queue.add(node.left);
                   queue.add(node.right);//将左右节点全部加入节点
               }else if (node.left != null){//如果做子节点不为空，说明已经有不是满二叉树的树结构，此时判断接下来的节点是否全部都是叶子节点
                   isSecType = true;//将标志位置为true，进入进入第二阶段
                   queue.add(node.left);
               }else if (node.right != null){//左节点不为空，右节点为空，不满足完全二叉树的要求（全部靠左排列）
                   return false;
               }else {//当节点全部为空时，也满足条件，进入第二阶段
                   isSecType = true;
               }
           }else {
               //如果进入遍历叶子节点阶段以后，还存在右孩子节点的节点，返回false；
               if (node.left != null || node.right != null){
                   return false;
               }
           }
        }
        return true;
    }
}
